package inner_sort

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"reflect"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/26 00:01
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 * */
type HeapSort struct {
	FromHighToLow bool // true表示从高到低排序,默认 false 表示从低到高排序
	IsSmallHeap   bool // IsSmallHeap = true:表示开启小顶堆，默认大顶堆
	gt            C.GT
	change        C.Change
}

func NewHeapSort(options ...C.Options) *HeapSort {
	opt := C.NewOptions(options...)
	gt := opt.GT
	if gt == nil {
		gt = C.ArrayGT
	}
	change := opt.Change
	if change == nil {
		change = C.ArrayChange()
	}
	return &HeapSort{
		IsSmallHeap: opt.IsSmallHeap,
		gt:          gt,
		change:      change,
	}
}

func (m *HeapSort) SortMethod(array []int) {
	if len(array) < 2 {
		return
	}
	n := len(array)
	/*建堆 tips:长度为n的数组，最后一个非叶子结点的index是: (n-1)/2
	推导：index为k的非叶子结点的左右孩子index分别是：2k+1、2k+2，所以为了求出确切的k值，index为n的孩子结点的父节点是：(n-1)/2
	应用：array最后一个叶子结点的index：n=len(array_relevant)-1，最后一个非叶子结点的index：（len(array_relevant)-1-1）/2 = len(array_relevant)/2-1*/
	for i := n/2 - 1; i >= 0; i-- {
		m.BuildHeapDown(array, i, n-1)
	}
	// 整堆
	for i := n - 1; i > 0; i-- {
		array[0], array[i] = array[i], array[0]
		m.BuildHeapDown(array, 0, i-1)
	}
}

// 顶堆
func (m *HeapSort) BuildHeapDown(array interface{}, parent, border int) {
	value := reflect.ValueOf(array)
	if value.Kind() != reflect.Array && value.Kind() != reflect.Slice {
		return
	}

	if border >= value.Len() || border <= 0 {
		return
	}
	child := parent*2 + 1 // 左孩子
	if child > border {
		return
	}
	if child+1 <= border { // 右孩子
		if m.IsSmallHeap && m.gt(array, child, child+1) {
			child = child + 1
		}
		if !m.IsSmallHeap && !m.gt(array, child, child+1) {
			child = child + 1
		}
	}
	if (m.IsSmallHeap && m.gt(array, child, parent)) || (!m.IsSmallHeap && !m.gt(array, child, parent)) {
		return
	}
	m.change(array, child, parent)
	m.BuildHeapDown(array, child, border)
}

func (m *HeapSort) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Sort},
		Desc: &C.Desc{
			Name:   "HeapSort",
			NameCn: "内部排序:堆排序:自顶向下",
			ParamsDesc: map[string]string{
				"fromHighToLow": "true表示从高到低排序, 默认 false 表示从低到高排序",
			},
			Example: map[int]string{
				1: "输入[1,3,2],跳用SortMethod方法进行排序后，输出[1,2,3]",
			},
		},
	}
}